import java.util.ArrayList;
import java.util.Scanner;

    public class TourGuide {
        private static final Site[] sites = new Site[7];//以地点代号循序存放地点
        private static final ArrayList<String> arrSites = new ArrayList<>();
        private static final double[][] matrix = new double[7][7];//用来存放地点间的路径长度(对角线为0，不存在为INFINITY)

        static {
            sites[0] = new Site(0, "入口", "欢迎进入动物园，祝你旅途愉快");//初始化存放地点的数组
            sites[1] = new Site(1, "狮子园", "内有举国闻名的大狮子，请勿投食");
            sites[2] = new Site(2, "猴山", "品种众多，及其具有灵性，请勿靠近，以免受伤");
            sites[3] = new Site(3, "老虎洞", "东北虎，极其稀有");
            sites[4] = new Site(4, "鸟林", "林中有丰富的鸟类，请勿伤害");
            sites[5] = new Site(5, "天鹅湖", "水上婀娜多姿的天鹅，使你心情更加愉悦");
            sites[6] = new Site(6, "熊猫基地", "可爱的国宝大熊猫");



            matrix[0][1] = 13;//初始化地点间的路径长度
            matrix[1][2] = 18;
            matrix[1][3] = 33;
            matrix[2][3] = 8;
            matrix[0][5] = 26;
            matrix[4][5] = 13;
            matrix[5][6] = 12;
            matrix[4][6] = 24;





            for (Site site : sites) arrSites.add(site.getName()); //初始化ArrayList,用于以字符串的形式按顺序存放地点的名字

            for (int i = 0; i < sites.length; i++) {//初始化地点间的路径长度
                for (int j = 0; j < sites.length; j++) {
                    if (i != j && matrix[i][j] == 0)
                        matrix[i][j] = Double.POSITIVE_INFINITY;
                    if (i > j)
                        matrix[i][j] = matrix[j][i];
                }
            }
        }

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int select;
            while (true) {
                System.out.println("   **欢迎使用景区导览电子地图**");
                System.out.println("【老虎洞】"+"———【狮子园】" + "——【入口】"+"——【天鹅湖】"+"——【鸟林】" );
                System.out.println("    |"+"        |"+"        "+"             |"+"       |");
                System.out.println("    |"+"______【猴山】"+"       "+"     【熊猫基地】" +"____|");
                System.out.println("1.查询景点相关信息\n2.查询两景点之间的最短距离\n3.修改两景点之间的道路信息\n4.更新景点信息");

                select = scanner.nextInt();
                switch (select) {
                    case 1:
                        System.out.print("输入查询地点的名称: ");
                        String siteIntro = query(scanner.next());
                        if (siteIntro != null) {//其实这里也可以直接arrSites.indexOf(name)判断
                            System.out.println(siteIntro);
                        } else {
                            System.err.println("输入的地点名称不存在!");
                        }
                        break;
                    case 2:
                        System.out.print("请输入两景点间所求路径: ");
                        String path = findShortestPath(scanner.next());
                        if (path != null) {
                            System.out.println(path);
                        } else {
                            System.err.println("输入的所要查询最短路径的两地的名称或者格式有误!");
                        }
                        break;
                    case 3:
                        System.exit(0);
                    default:
                        System.err.println("输入的选项有误!");
                }
                System.out.println();
            }
        }

        public static String query(String siteName) {
            int index = arrSites.indexOf(siteName);
            if (index == -1) {
                return null;
            } else {
                return sites[index].getIntro();
            }
        }

        public static String findShortestPath(String path) {
            int indexOfSeparator = path.indexOf('-');
            if (indexOfSeparator == -1) return null;
            String start = path.substring(0, indexOfSeparator);
            String end = path.substring(indexOfSeparator + 1);
            int indexOfStart = arrSites.indexOf(start);
            int indexOfEnd = arrSites.indexOf(end);
            if (indexOfStart == -1 || indexOfEnd == -1) return null;
            return dijkstra(indexOfStart, indexOfEnd);
        }

        private static String dijkstra(int start, int end) {
            int vertexCount = TourGuide.matrix.length;
            boolean[] isInUSet = new boolean[vertexCount];//数组元素默认初始化为false
            double[] distant = new double[vertexCount];
            int[] parent = new int[vertexCount];
            for (int i = 0; i < vertexCount; i++) {
                distant[i] = TourGuide.matrix[start][i];
                parent[i] = start;
            }
            isInUSet[start] = true;
            distant[start] = 0;
            parent[start] = -1;

            for (int i = 0; i < vertexCount; i++) {
                double minCost = Double.POSITIVE_INFINITY;
                int minIndex = start;
                for (int j = 0; j < vertexCount; j++) {
                    if (!isInUSet[j])
                        if (distant[j] < minCost) {
                            minCost = distant[j];
                            minIndex = j;
                        }
                }
                if (minCost < Double.POSITIVE_INFINITY) {
                    isInUSet[minIndex] = true;
                } else {
                    break;      //处理的图为非连通图,即不输出相应路径(不存在能达到该顶点的路径)
                }
                if (minIndex == end)//找到后直接return提高效率
                    return printDijkstra(parent, distant, start, end);
                for (int j = 0; j < vertexCount; j++) {//迭代优化
                    if (!isInUSet[j] && distant[minIndex] + TourGuide.matrix[minIndex][j] < distant[j]) {
                        distant[j] = distant[minIndex] + TourGuide.matrix[minIndex][j];
                        parent[j] = minIndex;
                    }
                }
            }
            return null;
        }

        private static String printDijkstra(int[] parent, double[] distant, int start, int end) {
            int p = parent[end];
            StringBuilder path = new StringBuilder(arrSites.get(end));
            while (p != -1) {
                path.insert(0, arrSites.get(p) + "->");
                p = parent[p];
            }
            return arrSites.get(start) + "->" + arrSites.get(end) + " [" + path + "]: " + distant[end];
        }
    }

    class Site {
        private int code;
        private String name;
        private String intro;

        public Site(int code, String name, String intro) {
            this.code = code;
            this.name = name;
            this.intro = intro;
        }

        public int getCode() {
            return code;
        }

        public void setCode(int code) {
            this.code = code;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getIntro() {
            return intro;
        }

        public void setIntro(String intro) {
            this.intro = intro;
        }
    }

